/**
 * 归并排序:把两个或者多个已经有序的序列合并成一个序列（一般采用二路归并）
 * 二路归并：把两个或者多个有序序列合并成一个。
 * m路归并，至少要比较关键字m-1次
 * 
 * 2路归并排序形态上就像一个倒立的二叉树，归并趟数为(h-1)趟，即log2(n)
 * 
 * 空间复杂度:O(n)来源于辅助数组大小B[n]
 * 时间复杂度:
 * 		每一趟时间复杂度为O(n)
 * 		平均时间复杂度:O(log2(n))
 * 算法稳定性:不稳定
 * 
 * 稳定性：稳定的
 */

#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

int n=10;
int* B=(int* )malloc(sizeof(int)*n);	//辅助数组B

/**
 * @brief 归并算法
 * 
 * @param A 带归并的数组A
 * @param high ：第二个有序序列的第一个元素索引
 * @param low ：第一个有序序列的第一个元素索引
 * @param mid ：第一个有序序列的最后一个元素索引
 */
void Merge(int A[], int low, int mid, int high);

//合并排序
void MergeSort(int A[], int low, int high);

//打印
void print(int A[], int n);


int main()
{
	int a[10]={12,43,16,22,63,98,66,90,20,26};
	return 0;
}

void MergeSort(int A[], int low, int high)
{
	if(low<high)
	{
		int mid=(low+high)/2;//从中间划分为两个子序列
		MergeSort(A, low, mid);	//对左侧子序列递归的进行归并排序
		MergeSort(A, mid+1, high);//对右侧子序列递归的进行归并排序
		Merge(A, low, mid, high);//归并
	}
}

void Merge(int A[], int low, int mid, int high)
{
	//表A[low,mid]和A[mid+1,high]各自有序，将它们合并成一个表
	int i,j,k;
	for(int k=low; k<=mid; k++) B[k]=A[k];	//将A中所有元素复制到辅助数组B中
	//i为第一个表中的索引，j为第一个表中的索引，k为A数组的索引,i<=mid,j<=high
	for(i=low, j=mid+1, k=i; i<=mid && j<=high; k++)
	{
		if(B[i]<B[j]) A[k++] = B[i++];	//比较B的左右两段中的元素，元素小的从辅助数组拿出放到A数组中
		else A[k++] = B[j++];			//辅助数组索引i(j)+1，且A数组索引k+1
	}
	while(i<=mid) A[k++]=B[i++];//若第一个表未检测完，则将第一个表中剩下的元素复制到A数组中
	while(j<=high) A[k++]=B[j++];//若第二个表未检测完，则将第二个表中剩下的元素复制到A数组中
}

void print(int A[], int n)
{
	for(int i=0;i<n;i++)
	{
		printf("%d ",A[i]);
	}
	printf("\n");
}